package sit.engreal.leetcode.problems800;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.stream.Stream;

/**
 * <a herf="https://leetcode.cn/problems/flood-fill/">733. 图像渲染</a>
 */
public class LeetCode733 {
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        final int m = image.length;
        final int n = image[0].length;

        final ArrayDeque<int[]> deque = new ArrayDeque<>();
        int[][] answer = new int[m][];
        for (int i = 0; i < m; i++) {
            answer[i] = Arrays.copyOf(image[i], n);
        }

        int init = image[sr][sc];
        if (init == color) {
            return answer;
        }
        deque.offerLast(new int[]{sr, sc});
        while (!deque.isEmpty()) {
            final int[] p = deque.pollFirst();
            final int r = p[0];
            final int c = p[1];

            answer[r][c] = color;
            if (r - 1 >= 0 && answer[r - 1][c] == init && answer[r - 1][c] != color) {
                deque.offerLast(new int[]{r - 1, c});
            }
            if (r + 1 < m && answer[r + 1][c] == init && answer[r + 1][c] != color) {
                deque.offerLast(new int[]{r + 1, c});
            }
            if (c - 1 >= 0 && answer[r][c - 1] == init && answer[r][c - 1] != color) {
                deque.offerLast(new int[]{r, c - 1});
            }
            if (c + 1 < n && answer[r][c + 1] == init && answer[r][c + 1] != color) {
                deque.offerLast(new int[]{r, c + 1});
            }
        }
        return answer;
    }

    public static void main(String[] args) {
        final LeetCode733 demo = new LeetCode733();
        {
            final int[][] image = {{1, 1, 1}, {1, 1, 0}, {1, 0, 1}};
            final int[][] answer = demo.floodFill(image, 1, 1, 2);
            Stream.of(answer).map(Arrays::toString).forEach(System.out::println);
        }

        {

            final int[][] image = {{0, 0, 0}, {0, 0, 0}};
            final int[][] answer = demo.floodFill(image, 0, 0, 2);
            Stream.of(answer).map(Arrays::toString).forEach(System.out::println);
        }
    }

}
